package com.litchishell.others;

/**
 * @author LitchiShell
 * @description: leetCode链接:https://leetcode-cn.com/problems/reach-a-number/
 * @create 2022-04-11
 */
public class Code02 {

    public static void main(String[] args) {
        System.out.println(reachNumber(15));
    }

    /**
     * 一开始在0位置，每次都可以向左或者向右跳，
     * 第i次能向左或者向右跳严格的i步，
     * 请问从0到x位置，至少跳几次可以到达。
     * @param target
     * @return
     */
    public static int reachNumber(int target) {
        if(target == 0) {
            return 0;
        }

        target = Math.abs(target);
        long l = 0;
        long r = target;
        long m = 0;
        long near = 0;
        while (l <= r) {
            m = (l + r) / 2;
            if(sum(m) >= target) {
                near = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if (sum(near) == target) {
            return (int)near;
        }
        if (((sum(near) - target) & 1) == 1) {
            near++;
        }
        if (((sum(near) - target) & 1) == 1) {
            near++;
        }
        return (int)near;
    }

    public static long sum(long n) {
        return (n * (n + 1)) / 2;
    }
}
